package p2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2023-10-24
 * Time: 14:42
 */

import java.util.Scanner;

/**
 * 找第k小的数
 * 设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。
 *
 * 提示：函数int partition(int a[],int left,int right)的功能是根据a[left]~a[right]中的某个元素x（如a[left])对a[left]~a[right]进行划分，划分后的x所在位置的左段全小于等于x,右段全大于等于x,同时利用x所在的位置还可以计算出x是这批数据按升非降序排列的第几个数。因此可以编制int find(int a[],int left,int right,int k)函数，通过调用partition函数获得划分点，判断划分点是否第k小，若不是，递归调用find函数继续在左段或右段查找。
 *
 * 输入格式:
 * 输入有两行：
 *
 * 第一行是n和k，0<k<=n<=10000
 *
 * 第二行是n个整数
 *
 * 输出格式:
 * 输出第k小的数
 */
public class exp3_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int []arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        int res = find(arr, 0, n-1,k);
        System.out.println(res);
    }

    private static int find(int[] arr, int left, int right, int k) {
        if(left == right){
            return arr[left];
        }
        //划分数组并获取划分点位置
        int p = partition(arr, left, right);
        int rank = p - left + 1;
        if( rank == k){
            return arr[p];
        } else if(rank>k) {
            return find(arr, left, p-1,k);
        } else {
            return find(arr, p+1, right,k - rank);
        }
    }

    //挖坑法找基准
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while(left  <right){
            while(left < right && arr[right] >= pivot){
                right--;
            }
            arr[left] = arr[right];
            while(left<right && arr[left] <= pivot){
                left++;
            }
            arr[right] = arr[left];
        }
        //将基准放到正确的位置上
        arr[right] = pivot;
        return left;
    }
}
